1. Field of the Invention
The invention relates generally to communication systems, and more particularly to controlling outliers in offered load estimation in a shared medium communication network.
2. Discussion of Related Art
In today""s information age, there is an increasing need for high-speed communication networks that provide Internet access and other on-line services for an ever-increasing number of communications consumers. To that end, communications networks and technologies are evolving to meet current and future demands. Specifically, new networks are being deployed which reach a larger number of end users, and protocols are being developed to utilize the added bandwidth of these networks efficiently.
One technology that has been widely employed and will remain important in the foreseeable future is the shared medium communication network. A shared medium communication network is one in which a single communications channel (the shared channel) is shared by a number of users such that uncoordinated transmissions from different users may interfere with one another. The shared medium communication network typically includes a number of secondary stations that transmit on the shared channel, and a single primary station situated at a common receiving end of the shared channel for, among other things, coordinating access by the secondary stations to the shared channel. Since communication networks typically have a limited number of communication channels, the shared medium communication network allows many users to gain access to the network over a single communication channel, thereby allowing the remaining communication channels to be used for other purposes.
Many techniques are known, which the primary station can use for coordinating access by the secondary stations to the shared channel. The ability of the primary station to meet specified performance goals depends on a number of factors, including the particular technique(s) employed and the number of secondary stations attempting to access the shared channel at any given time. (The rate at which secondary stations are attempting to access the shared channel at a specific time is often referred to as the xe2x80x9coffered loadxe2x80x9d at this specific time). Furthermore, the ability of the primary station to meet specified performance goals often depends on the ability of the primary station to adapt to changes in the offered load over time, and more specifically on how quickly the primary station can adapt to such changes. Thus, the primary station must be able to estimate the offered load of the network and react accordingly.
Protocols that are employed to coordinate access to the shared channel are often referred to as Medium Access Control (MAC) protocols. MAC protocols fall into two basic categories: contention-free and contention-based protocols. In contention-free protocols, end users access a shared channel in a controlled manner such that transmissions are scheduled either statically or adaptively so that collisions are completely avoided. In contention-based protocols, users contend with one another to access channel resources. Collisions are not avoided by design, but are either controlled by requiring retransmissions to be randomly delayed, or resolved using a variety of other contention resolution strategies.
An example of a contention-based MAC protocol is known as an ALOHA protocol. Its original version, which operates with continuous or unspotted time, is referred to as Unslotted ALOHA. Another version, which operates with discrete or slotted time, is referred to as Slotted ALOHA. The behavior and performance of Unslotted and Slotted ALOHA have been studied widely, and their maximum throughputs are well known to be 1/(2e) and 1/e, respectively.
Most contention-based protocols, including the ALOHA protocols, resolve collisions by using feedback information on the number of users involved in the collisions. If the number of conflicting transmissions can be determined from the feedback, then channel throughput arbitrarily close to one packet per packet transmission time is known to be achievable in principle, but with intractable complexity. More often than not, for the sake of simplicity, feedback information used is ternary indicating zero, one, or more transmissions, or binary indicating exactly one transmission or otherwise.
A shared channel is typically slotted in time, wherein a slotted ALOHA protocol or any other MAC protocols operating with slotted time can be employed for coordinating channel access. Many variations and extensions have been derived from the original slotted ALOHA protocol. In this protocol, and most of its derivatives, provided the probability of a new transmission and that of a retransmission in each slot are small, the throughput in a slot can be approximated by G(n) exp{xe2x88x92G(n)}, where G(n) is the offered load or attempt rate, which is a function of n that denotes the number of backlogged users at the beginning of a given slot. It follows that the maximum throughput of slotted ALOHA is 1/e=0.368, which is attained when G(n)=1. It is well known that ordinary slotted ALOHA is generally not stable. Various methods for stabilizing slotted ALOHA exist, and many of them resort to adaptive control of the backoff scheme based on one or more states of the contention process. When the actual values of these states are not observable, they are estimated by a variety of means.
The stability of slotted ALOHA can be controlled by means of a dynamic frame structure, based on an a-posteriori expected value of the backlog at the beginning of each frame. Rivest in xe2x80x9cNetwork Control by Bayesian Broadcast,xe2x80x9d published in the technical report at MIT/LCS/TM-287, MIT Lab. for Computer Science, 1985, proposed a Pseudo-Bayesian algorithm to maintain the attempt rate G(n) close to 1 by estimating the number, n, of backlogged users at the beginning of each slot. A minimum mean-squared error predictor for estimating the channel backlog in slotted ALOHA was proposed by Thomopoulos, in xe2x80x9cA Simple and Versatile Decentralized Control for Slotted ALOHA, Reservation ALOHA, and Local Area Networks,xe2x80x9d published in the IEEE Trans. on Communications, Vol. 36, No. 6, June 1988, for regulating the retransmission probability according to a recursive function of the channel backlog estimate.
The co-pending U.S. patent application Ser. No. 09/085,749 entitled OFFERED LOAD ESTIMATION AND APPLICATIONS FOR USING SAME IN A COMMUNICATION NETWORK by Firass Abi-Nassif and Whay Chiou Lee, filed on May 28, 1998, describes a method for estimating the offered load on the upstream of an HFC (Hybrid Fiber Coaxial) cable. The estimate is susceptible to degradation due to outliers. A need remains for enhancing the performance of the offered load estimator.
Parameter estimators, in general, make use of measured sample observations to determine the values of the parameters to be estimated. The presence of erroneous or misleading sample observations can lead to an unreliable estimation. Methods for identifying and handling sample observations are therefore essential in many estimation problems.
As defined in xe2x80x9cOutliers in Statistical Dataxe2x80x9d, 3rd Edition, Wiley 1994, by V. Barnett and T. Lewis, an observation in a set of data is considered an outlier if it appears to be inconsistent with the remainder of that set of data. Consider a univariate random sample of n observations originating from a distribution F. Suppose that they are ordered such that x(1) less than x(2) less than  . . .  less than x(n). Observations close to, and including x(1) and x(n), are referred to as extremes. An observation that originates from another distribution H, but not from F, is referred to as a contaminant. There exist statistical methods, named discordancy tests, which can be used to examine an outlier as a potential contaminant, or to determine if an observation is statistically dubious in relation to a given distribution of observations.
In multivariate samples, a simple ordering of the multivariate observations in an increasing/decreasing order is inapplicable. One alternative, referred to as xe2x80x9creduced sub-orderingxe2x80x9d, is to identify a scalar metric that characterizes the xe2x80x9cextremenessxe2x80x9d of observations. For example, when the underlying sample distribution is a normal distribution, one could use a quadratic distance measure.
Three ways to handle outliers after assessing that they are discordant are presented by V. Barnett, in xe2x80x9cOutliers and Order Statisticsxe2x80x9d, published in Communications Statistics-Theory, 1988. 17 (7), 2109-2118. The first, referred to as xe2x80x9cincorporationxe2x80x9d, consists of altering the underlying distribution F so that no observation vector appears to be discordant. The second method, referred to as xe2x80x9cidentificationxe2x80x9d, uses a discordant outlier to discover a new important characteristic of the corresponding population. The third method, referred to as xe2x80x9crejectionxe2x80x9d, is to simply reject the observation vector. This rejection method should be utilized when the knowledge of the underlying distribution is very accurate and xe2x80x9cinviolablexe2x80x9d.
In many complex systems, it is often desirable to infer system state information based on a limited number of observations in the system. Specifically, a number of sample observations are made in order to obtain a number of sample values. The number of sample values represents a sample value combination from among a set of possible sample value combinations. Unfortunately, when only a limited number of observations are made, the inferred system state information may or may not be an accurate representation of the true state of the system. In the co-pending U.S. patent application Ser. No.09/085,749 entitled OFFERED LOAD ESTIMATION AND APPLICATIONS FOR USING SAME IN A COMMUNICATION NETWORK, offered load estimates are susceptible to degradation due to outliers. Therefore, a need remains for a method and a device for controlling outliers in offered load estimation in a shared medium communication network.
In the preferred embodiment of the present invention, a method and device for outlier control of contention outcomes in a shared medium communication network is described which includes collecting a set of sample values being formed using contention outcomes of a plurality of contention intervals and partitioning the set of sample values according to a predetermined scheme the scheme being based on a measure of proximity to a locus of expected sample values, into a set of trusted sample values and a set of untrusted sample values. The untrusted sample values are rejected and the trusted sample values are accepted.